package gold.digger;

import gold.utils.InputUtil;

import java.util.Arrays;

/**
 * Created by fanzhenyu02 on 2021/12/10.
 * common problem solver template.
 */
public class LC2359 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        public int closestMeetingNode(int[] edges, int node1, int node2) {
            int n = edges.length, ans = -1, minCommonDis = Integer.MAX_VALUE;
            int[] fromSrcDis01 = new int[n], fromSrcDis02 = new int[n];
            Arrays.fill(fromSrcDis01, Integer.MAX_VALUE);
            Arrays.fill(fromSrcDis02, Integer.MAX_VALUE);

            BFS(edges, node1, 0, fromSrcDis01, new boolean[n]);
            BFS(edges, node2, 0, fromSrcDis02, new boolean[n]);

            for (int i = 0; i < n; i++) {
                int curMaxDis = Math.max(fromSrcDis01[i], fromSrcDis02[i]);
                if (curMaxDis < minCommonDis) {
                    minCommonDis = curMaxDis;
                    ans = i;
                }
            }

            return ans;
        }

        public void BFS(int[] edges, int cur, int depth, int[] fromSrcDis, boolean[] visited) {
            fromSrcDis[cur] = depth;
            visited[cur] = true;

            int next = edges[cur];
            if (-1 == next || visited[next]) return;
            BFS(edges, next, depth + 1, fromSrcDis, visited);
        }
    }

    public void run() {
        System.out.println(new Solution().closestMeetingNode(InputUtil.toIntegerArray("[2,2,3,-1]"), 0, 1));
        System.out.println(new Solution().closestMeetingNode(InputUtil.toIntegerArray("[1,2,-1]"), 0, 2));
    }

    public static void main(String[] args) throws Exception {
        LC2359 an = new LC2359();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
